package leetcode_day._2021._202107._0110;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/7/3 21:21
 * 根据字符出现频率排序
 * 算法：优先队列（堆）
 * 先用哈表表存储字符出现的次数
 * 构造一个节点存入优先队列中
 */
public class _03_451 {
    class Node {
        char c;
        int count;
        Node(char c, int count) {
            this.c = c;
            this.count = count;
        }
    }

    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        for (char c : chars) map.put(c, map.getOrDefault(c, 0) + 1);
        Queue<Node> priorityQueue = new PriorityQueue<>(map.size(), (a, b) -> {
            if (a.count != b.count) return b.count - a.count;
            return a.c - b.c;
        });
        for (Map.Entry<Character, Integer> entry : map.entrySet())
            priorityQueue.offer(new Node(entry.getKey(), entry.getValue()));
        StringBuilder ans = new StringBuilder();
        while (!priorityQueue.isEmpty()) {
            Node poll = priorityQueue.poll();
            char c = poll.c;
            for (int i = 0; i < poll.count; i++) ans.append(c);
        }
        return ans.toString();
    }

}
